 Micarea cailor.

 Pe o tabl de ah n(n  se gsesc p  cai i k obstacole amplasate ntr-o  configuraie iniial. Micarea calului este cea cunoscuta de la ah.  Calul poate sri un obstacol sau un alt cal, dar nu poate staiona pe o poziie ocupat  de un cal  sau de un obstacol.     

 Problema cere ca dvs. s   determinai, dac exist,  un set de micri ale  cailor care permit ajungerea ntr-o configuraie final cerut.  Exemplu:

Configuraie iniial (n=3, p=2, k=1) .


  





Configuraie final.







  Observaii:

1. Configuraia iniial se citete din fiierul text in.txt. Prima linie a fiierului conine numrul  n. Fiecare linie, din urmtoarele n, conine n caractere ( O pentru obstacol, C pentru cal,  S pentru csu neocupat. Urmtoarele n linii rein configuraia iniial (de sus n jos).  Pentru exemplul anterior  avem:

3
COC
SSS
SSS

2.  Programul va scrie soluia, dac exist, n fiierul out.txt.  Primele n linii vor fi date de configuraia iniial, urmeaz o linie vid, urmeaz n linii ale primei configuraii intermediare, o linie vid,  ,,,,, n linii ale configuraiei finale.  

3. Valorile p i k se deduc din configuraia iniial
4. 3(N(10
5 Daca nu exista solutie, prima linie a fisierului va contine NU 
6.  Timp de execuie: 1 minut.


 BOSNIA
Un teritoriu asimilat cu un ptrat de latur n (3 ( n ( 60) este locuit de srbi i musulmani. Pe fiecare unitate de suprafa se cunoate numrul de srbi i respectiv numrul de musulmani ce locuiesc n ptratul unitar corespunztor.
Organizaia Naiunilor Unite are la dispoziie cel mult n uniti militare pe care le poate amplasa n teritoriu, fiecare pe un ptrel, pentru a delimita exact dou suprafee, una atribuit srbilor, cealalt atribuit musulmanilor. Se urmrete prin aceast mprire a teritoriului ca densitatea populaiei srbe din zona atribuit srbilor s fie ct mai apropiat valoric de densitatea musulmanilor din zona atribuit musulmanilor. 
Observaii: 
 Densitatea unei populaii X se calculeaz ca raport ntre totalul populaiei X i numrul de ptrele aparinnd zonei atribuite poporului X.
 Din considerente matematice se ignor locuitorii srbi din zona musulman, locuitorii musulmani din zona srb i locuitorii srbi i musulmani din ptrele ocupate de amplasamentele ONU.
Unitile trebuie s fie amplasate astfel nct ele s formeze o linie continu ce unete dou laturi opuse ale teritoriului. Dou uniti se consider nvecinate (n sensul continuitii) dac au o latur comun sau un col comun. Nici o unitate ONU nu poate ocupa vreunul dintre colurile ptratului reprezentnd teritoriul.

Datele de intrare se citesc din fiierul ONU.IN cu urmtorul format:
n				- latura ptratului;
s11 s12 ... s1n
s21 s22 ... s2n		- numrul locuitorilor srbi din fiecare ptrat unitar 
...					(numere naturale de cel mult dou cifre)
sn1 sn2 ... snn
m11 m12 ... m1n
m21 m22 ... m2n		- numrul locuitorilor musulmani din fiecare ptrat unitar 
...					(numere naturale de cel mult dou cifre)
mn1 mn2 ... mnn

Datele de ieire se scriu n fiierul ONU.OUT cu urmtorul format:
k		- numrul de uniti amplasate
l1 c1
l2 c2		- cooordonatele (linie coloan) ale fiecrei uniti amplasate
...				n ordinea lexicografic a perechilor
lk ck
L1		- liter desemnnd poporul care ocup ptrelul de coordonate 1,1
L2		- liter desemnnd poporul care ocup ptrelul de coordonate n,n
			(L1,L2 ({S,M}
Se furnizeaz rezultatele:
3
2 1
2 2
2 3
S
M
Exemplu:
3
1  2  0
3  2  2
4  1  2
5  0  0
4  2  1
0  0  3
Timp limit de execuie : 30 secunde
